public class Solution32 {

    public int longestValidParentheses(String s) {
        int length = s.length();
        if(length < 2){
            return 0;
        }
        int[] dp = new int[length];
        int res = 0;
        for (int i = 1; i < length; i++) {
            if(s.charAt(i) == ')'){
                int tmpDpNum = 0;
                if(s.charAt(i - 1) == '('){
                    tmpDpNum = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                }
                else{
                    int lastDpNum = dp[i - 1];
                    int matchInd = i - 1 - lastDpNum;
                    if(matchInd >= 0 && s.charAt(matchInd) == '('){
                        tmpDpNum = (matchInd - 1 >= 0 ? dp[matchInd - 1] : 0) + lastDpNum + 2;
                    }
                }
                dp[i] = tmpDpNum;
                res = Math.max(res, tmpDpNum);
            }
        }
        return res;
    }
}
